package com.maishi.programmer.jainzhioffer;

/**
 * Created by brossdong on 2018/4/10.
 * 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。
 * 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 */
public class TestProblem49 {

    public static int getUglyNumber_Solution2(int index){

        if (index <= 0) return 0;
        //创建一个数组
        int[] uglyArray = new int[index];
        uglyArray[0] = 1;
        //定义最大臭数后面的数
        int ugly2 = 0;
        int ugly3 = 0;
        int ugly5 = 0;
        for (int i = 1;i < index;i++) {
            int min = min(uglyArray[ugly2] * 2,uglyArray[ugly3] * 3,uglyArray[ugly5] * 5);
            uglyArray[i] = min;
            while (uglyArray[ugly2] * 2 == uglyArray[i])
                ugly2++;
            while (uglyArray[ugly3] * 3 == uglyArray[i])
                ugly3++;
            while (uglyArray[ugly5] * 5 == uglyArray[i])
                ugly5++;
        }
        return uglyArray[index - 1];
    }

    public static int min (int num1,int num2,int num3) {
        int min = (num1 < num2) ? num1 : num2;
        return min < num3 ? min : num3;
    }

    public static void main(String[] args) {
        int uglyNumber_solution2 = getUglyNumber_Solution2(0);
        System.out.println(uglyNumber_solution2);
    }
}
